#include "backtracking.h"

BackTracking::BackTracking() {}

TreeNode* BackTracking::CreatTree(const std::vector<int>& nums, int i = 0) {
    if(nums.empty() || i >= nums.size() || nums[i] == -1) {
        return nullptr;
    }
    TreeNode* root_node_ = new TreeNode(nums[i]);  // 创建根节点
    root_node_->left = CreatTree(nums,2 * i + 1);  // 创建左子树
    root_node_->right = CreatTree(nums,2 * i + 2); // 创建右子树

    return root_node_;

}

void BackTracking::freeTree(TreeNode* root) {
    if(root == nullptr) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    delete root;
    return;
}

void BackTracking::printTree(TreeNode* root) {
    if(root == nullptr) {
        return;
    }
    std::queue<TreeNode*> myQueue;
    myQueue.push(root);
    while(!myQueue.empty()) {
        TreeNode* node = myQueue.front();
        myQueue.pop();
        std::cout << node->val << " ";
        if(node->left) myQueue.push(node->left);
        if(node->right) myQueue.push(node->right);
    }
    std::cout << "\n";

    return;
}

void BackTracking::preOrderWith7(TreeNode* root) {
    if(root == nullptr) {
        return;
    }
    if(root->val == 7) {
        std::cout << "find node that the value is 7:" << root->val << std::endl;
    }
    preOrderWith7(root->left);
    preOrderWith7(root->right);
    return;
}

void BackTracking::preOrderWith7path(TreeNode* root,std::vector<int>& path,std::vector<std::vector<int>>& res) {
    if(root == nullptr) {
        return;
    }

    // 尝试
    path.push_back(root->val);
    if(root->val == 7) {
        // 记录解
        res.push_back(path);
    }
    preOrderWith7path(root->left,path,res);
    preOrderWith7path(root->right,path,res);
    // 回退
    path.pop_back();
    return;
}

void BackTracking::preOrderWith7pathNo3(TreeNode* root,std::vector<int>& path,std::vector<std::vector<int>>& res) {
    if(root == nullptr || root->val == 3) {
        return;
    }

    // 尝试
    path.push_back(root->val);
    if(root->val == 7) {
        // 记录解
        res.push_back(path);
    }
    preOrderWith7pathNo3(root->left,path,res);
    preOrderWith7pathNo3(root->right,path,res);
    // 回退
    path.pop_back();
    return;
}


void BackTracking::backtrackingforPermutationsI(std::vector<int>& state,const std::vector<int>& choices,
                                     std::vector<bool>& selected,std::vector<std::vector<int>> &res) {
    // 当状态长度等于元素数量时，记录解并返回
    if(state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 循环遍历所有元素
    for(int i = 0; i < choices.size();i++) {
        int choice = choices.at(i);
        // 剪枝，不允许相同元素
        if(!selected.at(i)) {
            // 尝试，做出选择，更新状态
            selected.at(i) = true;
            state.push_back(choice);
            // 进行下一轮选择
            backtrackingforPermutationsI(state,choices,selected,res);
            // 恢复状态
            selected.at(i) = false;
            state.pop_back();
        }
    }
}

void BackTracking::backtrackingforPermutationsII(std::vector<int> &state,const std::vector<int>& choices,
                                     std::vector<bool>& selected,std::vector<std::vector<int>> &res) {
    // 当状态长度等于元素数量时，记录解并返回上一层
    if(state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    std::unordered_set<int> duplicated;
    for(int i = 0;i < choices.size();i++) {
        int choice = choices.at(i);
        // 剪枝 ，剪去同一个元素，并剪去值相同的元素
        if(!selected.at(i) && duplicated.find(choice) == duplicated.end()) {
            //做出选择，更新状态
            selected.at(i) = true;     // 记录选择过的元素，用于下一轮剪枝同一个元素
            duplicated.emplace(choice); //记录选择过的元素，用于下一轮筛选值相同的元素
            state.push_back(choice);
            // 进行下一轮选择
            backtrackingforPermutationsII(state,choices,selected,res);
            // 恢复状态
            selected.at(i) = false;
            state.pop_back();
        }

    }

}

void BackTracking::backtrackingforSubSetSumINaive(std::vector<int> &state,const std::vector<int>& choices,
                                        int total,int target,std::vector<std::vector<int>> &res) {
    // 如果子集和等于目标值时，记录解
    if(total == target) {
        res.push_back(state);
        return;
    }
    // 循环遍历所有选择
    for(int i = 0;i < choices.size();i++) {
        if(total + choices.at(i) > target) {
            continue;
        }
        // 尝试，做出选择，更新元素和total
        state.push_back(choices.at(i));
        // 进行下一轮选择
        backtrackingforSubSetSumINaive(state,choices,total + choices.at(i),target,res);
        // 回退,恢复状态
        state.pop_back();
    }
}

void BackTracking::backtrackingforSubSetSumI(std::vector<int> &state,const std::vector<int>& choices,
                                        int target,int start,std::vector<std::vector<int>> &res) {
    // 如果目标值等于0，说明子集和等于目标值，记录解
    if(target == 0) {
        res.push_back(state);
        return;
    } 
    // 从start开始循环遍历所有选择
    for(int i = start;i < choices.size();i++) {
        if(target - choices.at(i) < 0) {
            break;
        }
        // 尝试，做出选择，更新状态，target和start
        state.push_back(choices.at(i));
        // 进行下一轮选择
        backtrackingforSubSetSumI(state,choices,target - choices.at(i),i,res);
        // 回退，恢复状态
        state.pop_back();
    }
}

void BackTracking::backtrackingforSubSetSumII(std::vector<int> &state,const std::vector<int>& choices,
                                        int target,int start,std::vector<std::vector<int>> &res) {
    // 如果目标值等于0，说明子集和等于目标值，记录解
    if(target == 0) {
        res.push_back(state);
        return;
    }
    // 从start开始遍历，剪枝二，避免生成重复子集
    // 从start开始遍历，剪枝三，避免重复选择同一元素
    for(int i = start; i < choices.size();i++) {
        // 剪枝一：若子集和超过target，则直接结束循环
        // 已对数组进行排序，后边元素更大，子集和一定超过target
        if(target - choices.at(i) < 0) {
            break;
        }
        // 如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
        if(i > start && choices.at(i) == choices.at(i - 1)) {
            continue;
        }
        // 尝试，更新状态，target,start
        state.push_back(choices.at(i));
        // 进行下一轮选择
        backtrackingforSubSetSumII(state,choices,target - choices.at(i),i+1,res);
        // 回退，恢复状态
        state.pop_back();
    }
}

void BackTracking::backtrackingfornQueens(int row,int n,std::vector<std::vector<std::string>> &state,std::vector<bool>& cols,
                                std::vector<bool>& diags1,std::vector<bool>& diags2,
                                std::vector<std::vector<std::vector<std::string>>>& res) {
    // 所有行都填完时，回溯
    if(row == n) {
        res.push_back(state);
        return;
    }
    // 遍历所有列
    for(int col = 0;col < n;col++) {
        // 计算格子的主对角线与次对角线
        int diag1 = row - col + n - 1;
        int diag2 = row + col;
        // 剪枝，不允许该格子所在列，主对角线，次对角线存在皇后
        if(!cols[col] && !diags1[diag1] && !diags2[diag2]) {
            // 尝试:在该格子放置皇后
            state[row][col] = "Q";
            cols[col] = diags1[diag1] = diags2[diag2] = true;
            // 进行下一行的选择
            backtrackingfornQueens(row + 1,n,state,cols,diags1,diags2,res);
            // 回溯，将格子置空
            state[row][col] = "#";
            cols[col] = diags1[diag1] = diags2[diag2] = false;
        }
    }
}